package leetcode.top100;

/**
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * <p>
 * 注意:
 * <p>
 * 每个数组中的元素不会超过 100
 * 数组的大小不会超过 200
 * 示例 1:
 * <p>
 * 输入: [1, 5, 11, 5]
 * <p>
 * 输出: true
 * <p>
 * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
 *  
 * <p>
 * 示例 2:
 * <p>
 * 输入: [1, 2, 3, 5]
 * <p>
 * 输出: false
 * <p>
 * 解释: 数组不能分割成两个元素和相等的子集.
 * <p>
 * 同题见{@link baseclass.j_dp.dp.oneZeroBag.Code02_SumTargetInArr}
 * <p>
 * 同题见{@link baseclass.j_dp.dp.oneZeroBag.Code03_HalfSumArr}
 *
 * @date 2020/5/23 20:25
 */
public class Code416_分隔等和子集 {
    public static void main(String[] args) {
        Code416_分隔等和子集 test = new Code416_分隔等和子集();
        System.out.println(test.canPartition(new int[]{1, 2, 5}));
    }

    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0) return false;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //奇数
        if ((sum & 1) != 0) return false;
        return doCanPartition2(nums, sum / 2);
    }

    /**
     * 在数组nums中寻找能否组成aim。
     * dp[i][j]表示前i个元素能否组成和为j
     */
    private boolean doCanPartition(int[] nums, int aim) {
        boolean[][] dp = new boolean[nums.length][aim + 1];
        dp[0][0] = true;
        dp[0][aim] = nums[0] == aim;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= aim; j++) {
                //不要nums[i]
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i]) {
                    dp[i][j] = dp[i][j] | dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[nums.length - 1][aim];
    }

    /**
     * 空间优化
     */
    private boolean doCanPartition2(int[] nums, int aim) {
        boolean[] dp = new boolean[aim + 1];
        //第一个元素可以组成 0 或nums[0]
        dp[0] = true;
        if (nums[0] <= aim) dp[nums[0]] = true;

        for (int i = 1; i < nums.length; i++) {
            for (int j = aim; j >= nums[i]; j--) {
                //后一个dp[j]是当前不要nums[i]
                //dp[j-nums[i]]是当前位置要nums[i]
                dp[j] = dp[j] | dp[j - nums[i]];
            }
        }
        return dp[aim];
    }
}
